class Solution:
    def get_pre(self, s):
        j, pre = 0, [0] * len(s)
        for i in range(1, len(s)):
            while j > 0 and s[i] != s[j]:
                j = pre[j - 1]
            if s[i] == s[j]:
                j += 1
            pre[i] = j
        return pre

    def strStr(self, haystack: str, needle: str) -> int:
        j, pre = 0, self.get_pre(needle)
        for i in range(len(haystack)):
            while j > 0 and haystack[i] != needle[j]:
                j = pre[j - 1]
            if haystack[i] == needle[j]:
                j += 1
            if j == len(needle):
                return i - j + 1
        return -1

if __name__ == '__main__':
    s = Solution()
    print(s.strStr("mississippi", "issip"))
    print(s.strStr("aa", "a"))
    print(s.strStr("a", "aa"))
    print(s.strStr("sadbutsad", "sad"))
    print(s.strStr("leetcode", "leeto"))